//节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。 
//
// 示例1: 
//
//  输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
// 输出：true
// 
//
// 示例2: 
//
//  输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [
//1, 3], [2, 3], [3, 4]], start = 0, target = 4
// 输出 true
// 
//
// 提示： 
//
// 
// 节点数量n在[0, 1e5]范围内。 
// 节点编号大于等于 0 小于 n。 
// 图中可能存在自环和平行边。 
// 
// Related Topics 图 
// 👍 19 👎 0

package com.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//Java：节点间通路
class P面试题RouteBetweenNodesLcci {
    public static void main(String[] args) {
        Solution solution = new P面试题RouteBetweenNodesLcci().new Solution();
        // TO TEST
        int[][] graph = {{0, 1}, {0, 2}, {1, 2}, {1, 2}};
        solution.findWhetherExistsPath(3, graph, 0, 2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
            //邻接表
            List<List<Integer>> adjacencyList = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                adjacencyList.add(new ArrayList<>());
            }
            for (int i = 0; i < graph.length; i++) {
                adjacencyList.get(graph[i][0]).add(graph[i][1]);
            }
            //记录节点是否处理过
            boolean[] visited = new boolean[n];
            //BFS
//           return bfsSearch(start, target, adjacencyList, visited);
            //DFS
            return dfs(start, target, adjacencyList, visited);
        }


        private boolean dfs(int start, int target, List<List<Integer>> adjacencyList, boolean[] visited) {
            if (start == target) {
                return true;
            }
            for (int i = 0; i < adjacencyList.get(start).size(); i++) {
                int node = adjacencyList.get(start).get(i);
                if (!visited[node]) {
                    visited[node] = true;
                    boolean dfs = dfs(node, target, adjacencyList, visited);
                    if (dfs) {
                        return true;
                    }
                }
            }
            return false;
        }

        /**
         * BFS
         *
         * @param start
         * @param target
         * @param adjacencyList
         * @param visited
         * @return
         */
        private boolean bfsSearch(int start, int target, List<List<Integer>> adjacencyList, boolean[] visited) {
            //使用队列记录当前节点，以及未遍历过的邻接节点
            Queue<Integer> queue = new LinkedList<>();
            queue.add(start);
            while (!queue.isEmpty()) {
                //当前节点
                int currentNode = queue.poll();
                //遍历邻接节点
                for (int i = 0; i < adjacencyList.get(currentNode).size(); i++) {
                    //邻接节点
                    int node = adjacencyList.get(currentNode).get(i);
                    //如果此邻接节点未访问过
                    if (!visited[node]) {
                        visited[node] = true;
                        //如果是要找的目标节点，返回true
                        if (node == target) {
                            return true;
                        }
                        //将此邻接节点加入队列
                        queue.add(node);
                    }
                }
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}